#! /bin/sh
# This is a shell archive, meaning:
# 1. Remove everything above the #! /bin/sh line.
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh (not csh) to create:
#   README
#   glib.c
#   graphtypes.h
#   input.form
#   main.c
#   makefile
#   match.c
#   output.form
#   test.in
# This archive created: Thu Feb 21 19:34:59 EST 1991
export PATH; PATH=/bin:/usr/bin:/usr/ucb:/usr/bin:/etc:/usr/etc:/usr/local/X11R4/bin:/usr/local/bin:/dimacs/u2/badics/bin:/dimacs/u2/badics/out:/usr/lib/news:.
if test -f 'README'
then
	echo shar: "will not over-write existing file 'README'"
else
cat << \SHAR_EOF > 'README'
-------------------------------------------------------------------------
The Match_C.shell file contains a program, written in C, for finding 
MAXIMUM-CARDINALITY MATCHING in UNDIRECTED graphs.  
-------------------------------------------------------------------------

This program was written by Ed Rothberg to implement H. Gabow's N-cubed 
non-weighted matching algorithm. For an explanation of the algorithm 
see JACM 23, pp221-34 .

MAIN PROGRAMS:
		- match

REQUIRED FILES:
		README input.form output.form makefile graphtypes.h glib.c main.c
		match.c

TO GET THESE FILES:
        Run the "Match_C.shell" file in the /bin/sh shell. 
		(It will unwrap itself.)

FILE DESCRIPTIONS: 
		input.form:  Describes the input formats for match.
		output.form: Describes output formats for match.
						***Format converters will be available soon to
						translate input and output files from and to the
						DIMACS Challenge format. Contributions are welcome. 
		
		test.in:  A sample input for match
		
        The others are source code files written in C language.

HOW TO MAKE THE PROBLEM-SOLVERS:

		match:  Solves maximum matching for undirected graphs presented in an 
		       adjacency-list format. 

		       Requires: graphtypes.h glib.c main.c match.c makefile
		
		       To compile: $make
		       To invoke: $match input_file
		
		      If no filename is given, a small help message appears. It always  
		      writes to standard out.  

/ This README file was written by DIMACS, and based on experiments with the
codes. /
  
       

SHAR_EOF
fi
if test -f 'glib.c'
then
	echo shar: "will not over-write existing file 'glib.c'"
else
cat << \SHAR_EOF > 'glib.c'
#include "graphtypes.h"
#include <stdio.h>
#include <math.h>

AddEdge (g,n,m,label)
Graph g;
int n,m,label;

{	Edge edge1,edge2;

	edge1 = (Edge) malloc(2*sizeof(struct edge_ent));
	edge2 = edge1 + 1;

	edge1->label = label;
	edge1->endpoint = m;
	edge1->otheredge = edge2;
	edge1->prevedge = NULL;
	edge1->nextedge = g[n].adj_list;
	if (edge1->nextedge != NULL)
		edge1->nextedge->prevedge = edge1;
	g[n].adj_list = edge1;
	g[n].degree++;

	edge2->label = label;
	edge2->endpoint = n;
	edge2->otheredge = edge1;
	edge2->prevedge = NULL;
	edge2->nextedge = g[m].adj_list;
	if (edge2->nextedge != NULL)
		edge2->nextedge->prevedge = edge2;
	g[m].adj_list = edge2;
	g[m].degree++;
}

Edge FindEdge(graph,i,j)
Graph graph;
int i,j;

{	Edge edge;

	edge = graph[i].adj_list;
	while (edge!=NULL && edge->endpoint!=j)
		edge = edge->nextedge;
	if (edge==NULL) return(NULL);
	else return(edge);
}

int RemoveEdge(graph,edge)
Graph graph;
Edge edge;

{	Edge other;
	int i,j;

	if (edge==NULL) return(0);
	other = edge->otheredge;
	i = other->endpoint;
	j = edge->endpoint;
	graph[i].degree--; graph[j].degree--;
	if (edge->prevedge == NULL) {
		graph[i].adj_list = edge->nextedge;
		if (edge->nextedge != NULL)
			edge->nextedge->prevedge = NULL;
		}
	else if (edge->nextedge == NULL)
        	(edge->prevedge)->nextedge = NULL;
	else {
		(edge->nextedge)->prevedge = edge->prevedge;
		(edge->prevedge)->nextedge = edge->nextedge;
		}
	if (other->prevedge == NULL) {
		graph[j].adj_list = other->nextedge;
		if (other->nextedge != NULL)
			other->nextedge->prevedge = NULL;
		}
	else if (other->nextedge == NULL)
		(other->prevedge)->nextedge = NULL;
	else {
		(other->nextedge)->prevedge = other->prevedge;
		(other->prevedge)->nextedge = other->nextedge;
		}
	free((edge < other) ? edge : other);
	return(1);
}

int NumEdges(g)
Graph g;
{	int i,size,edges;

	edges = 0;
	size = Degree(g,0);
	for (i=1; i<=size; i++)
		edges += Degree(g,i);
	edges /= 2;
	return(edges);
}

Graph NewGraph(size)
int size;
{	Graph tmp;
	int i;

	tmp = (Graph) malloc((size+1)*sizeof(struct node_entry));
	for (i=1; i<=size; i++) {
		Degree(tmp,i) = 0;
		FirstEdge(tmp,i) = NULL;
		NLabel(tmp,i) = i;
		}
	Degree(tmp,0) = size;
	return(tmp);
}

EuclidGraph NewEuclid(size)
int size;
{
	EuclidGraph xy;

	xy = (EuclidGraph) malloc((size+1)*2*sizeof(int));
	xy[0][0] = size;
	return(xy);
}

MatrixGraph NewMatrix(size)
int size;
{
	MatrixGraph graph;
	int i;

	graph = (MatrixGraph) malloc((size*(size+1)+1)*sizeof(int));
	graph[0] = size;

	for (i=1; i<=size; i++)		/* zero the diagonal */
		graph[i*(size+1)] = 0;

	return(graph);
}

Graph CopyGraph(g)
Graph g;
{	int i,j,size;
	Edge edge;
	Graph cp;

	size = Degree(g,0);
	cp = NewGraph(size);
	for (i=1; i<=size; i++) {
		Xcoord(cp,i) = Xcoord(g,i);
		Ycoord(cp,i) = Ycoord(g,i);
		edge = FirstEdge(g,i);
		for (j=1; j<=Degree(g,i); j++) {
			if (i < EndPoint(edge))
				AddEdge(cp,i,EndPoint(edge),ELabel(edge));
			edge = NextEdge(edge);
			}
		}
	return (cp);
}

/* Graph I/O routines */

Graph ReadGraph (size,file)
int *size;
char file[];

{	Graph graph;
	FILE *fp;
 	char c;
	int edges, degree, vlabel, elabel, adj_node, i, j;
	int xcoord, ycoord;

	if (file[0] == '\0') fp = stdin;
	else fp = fopen(file,"r");
	if (fp==NULL) {
		printf("ReadGraph: file %s can't be opened\n",file);
		exit(0);
		}
	fscanf(fp,"%d%d %c",size,&edges,&c);
	if (c !='U' && c!='u') {
		printf("ReadGraph: file %s does not contain an undirected graph\n",file);
		exit(0);
		}
	while (getc(fp)!='\n') ;

	graph = NewGraph(*size);
	for (i = 1; i <= *size; ++i) {
		fscanf(fp,"%d%d%d%d",&degree,&vlabel,&xcoord,&ycoord);
		NLabel(graph,i) = vlabel;
		Xcoord(graph,i) = xcoord;
		Ycoord(graph,i) = ycoord;
		while (getc(fp)!='\n') ;
		for (j = 1; j <= degree; ++j) {
			fscanf(fp,"%d%d", &adj_node, &elabel);
			while (getc(fp)!='\n') ;
			if (i<adj_node)
				AddEdge (graph,i,adj_node,elabel);
			}
		}
	fclose(fp);
	return(graph);
}

WriteGraph (graph,file)
Graph graph;
char file[];

{	FILE *fp;
	int size, i,j,edges;
	Edge p;

	if (file[0] == '\0') fp = stdout;
	else fp = fopen(file,"w");
	if (fp==NULL) {
		printf("WriteGraph: file %s can't be opened\n",file);
		exit(0);
		}
	size = Degree(graph,0);
	edges = NumEdges(graph);
	fprintf(fp,"%d %d U\n",size,edges);

	for (i = 1; i <= size; i++) {
		fprintf(fp,"%d %d %d %d L\n",Degree(graph,i),NLabel(graph,i),
					   Xcoord(graph,i),Ycoord(graph,i));
		p = FirstEdge(graph,i);
		for (j = 1; j <= Degree(graph,i); ++j) {
			fprintf(fp,"%d %d L\n",EndPoint(p),ELabel(p));
			p = NextEdge(p);
			}
		}
	fclose(fp);
}

EuclidGraph ReadEuclid(size,file)
int *size;
char file[];

{	EuclidGraph graph;
	FILE *fp;
	char c;
	int i,xcoord, ycoord;

	if (file[0]=='\0') fp=stdin;
	else fp = fopen(file,"r");
	if (fp==NULL) {
		printf("ReadEuclid: file %s can't be opened\n",file);
		exit(0);
		}
	fscanf(fp,"%d %c",size,&c);
	if (c!='E' && c!='e') {
		printf("ReadEuclid: file %s isn't Euclidean\n",file);
		exit(0);
		}
	while (getc(fp)!='\n');
	graph = NewEuclid(*size);

	for (i=1; i<=*size; ++i) {
		fscanf(fp,"%d%d",&xcoord,&ycoord);
		while (getc(fp)!='\n') ;
		graph[i][0] = xcoord;
		graph[i][1] = ycoord;
		}
	fclose(fp);
	return (graph);
}

WriteEuclid(graph,file)
EuclidGraph graph;
char file[];

{	FILE *fp;
	int size, i;

	if (file[0] == '\0') fp = stdout;
	else fp = fopen(file,"w");
	if (fp==NULL) {
		printf("WriteEuclid: file %s can't be opened\n",file);
		exit(0);
		}
	size = graph[0][0];
	fprintf(fp,"%d E\n",size);
	for (i = 1; i <= size; i++) 
		fprintf(fp,"%d %d\n",graph[i][0],graph[i][1]);
	fclose(fp);
}

MatrixGraph ReadMatrix(size,file)
int *size;
char file[];
{	MatrixGraph graph;
	FILE *fp;
	char c;
	int i,j,k;

	if (file[0]=='\0') fp=stdin;
	else fp = fopen(file,"r");
	if (fp==NULL) {
		printf("ReadMatrix: file %s can't be opened\n",file);
		exit(0);
		}
	fscanf(fp,"%d %c",size,&c);
	if (c!='M' && c!='m') {
		printf("ReadMatrix: file %s isn't a distance matrix\n",file);
		exit(0);
		}
	while (getc(fp)!='\n');
	graph = NewMatrix(*size);

	for (i=1; i<*size; i++) {
		for (j=i+1; j<=*size; j++) {
			fscanf(fp,"%d",&k);
			graph[i*(*size)+j] = graph[j*(*size)+i] = k;
			}
		while (getc(fp)!='\n');
		}
	fclose(fp);
	return(graph);
}

WriteMatrix(graph,file)
MatrixGraph graph;
char file[];

{	FILE *fp;
	int size, i, j;

	if (file[0] == '\0') fp = stdout;
	else fp = fopen(file,"w");
	if (fp==NULL) {
		printf("WriteMatrix: file %s can't be opened\n",file);
		exit(0);
		}
	size = graph[0];
	fprintf(fp,"%d M\n",size);
	for (i = 1; i < size; i++) {
		for (j=i+1; j<=size; j++)
			fprintf(fp,"%d ",graph[i*size+j]);
		fprintf(fp,"\n");
		}
	fclose(fp);
}

/* Euclidean distance routines */

int eucdist (graph,i,j) /* Find the distance between two points */
			/* 10K x 10K unit square */
EuclidGraph graph;
int i,j;
{	int dv,dh;
	register int k, l;

	dv = graph[i][0]-graph[j][0];
	dh = graph[i][1]-graph[j][1];
	k = dv*dv + dh*dh;
	if (k==0) return(0);
	if (dv<0) dv = -dv;
	if (dh<0) dh = -dh;
	l = dv + dh;
	l = (l + k/l)>>1;
	l = (l + k/l)>>1;
	l = (l + k/l)>>1;
	l = (l + k/l)>>1;
	return ((l*l<k) ? ++l : l);
}


int eucdist2 (graph,i,j) /* Find the distance between two points */
			/* 1M x 1M unit square */
EuclidGraph graph;
int i,j;
{	double dv,dh,d;
	int l;

	dv = (double) graph[i][0]-graph[j][0];
	dh = (double) graph[i][1]-graph[j][1];
	d  = sqrt(dv*dv + dh*dh);
	l  = (int) d;
	return((d-l > .000000001) ? l+1 : l);
}


int eucdistsq(graph,i,j) /* Find the square of the dist between two points */
EuclidGraph graph;
int i,j;
{
	register int dv,dh;

	dv = graph[i][0]-graph[j][0];
	dh = graph[i][1]-graph[j][1];
	return(dv*dv+dh*dh);
}

SHAR_EOF
fi
if test -f 'graphtypes.h'
then
	echo shar: "will not over-write existing file 'graphtypes.h'"
else
cat << \SHAR_EOF > 'graphtypes.h'
#define INF	100000000
#define NULL	0

struct node_entry {
    int degree;
    int label;
    int x;
    int y;
    struct edge_ent *adj_list;
    };
typedef struct node_entry *Graph;

struct edge_ent {
    int endpoint;
    int label;
    int label2;
    struct edge_ent *nextedge;
    struct edge_ent *prevedge;
    struct edge_ent *otheredge;
    };
typedef struct edge_ent *Edge;

extern Graph ReadGraph(),NewGraph(),CopyGraph();
extern int RemoveEdge(),NumEdges();
extern Edge FindEdge();

#define Degree(graph,n)    (graph[n].degree)
#define NLabel(graph,n)    (graph[n].label)
#define Xcoord(graph,n)    (graph[n].x)
#define Ycoord(graph,n)    (graph[n].y)
#define FirstEdge(graph,n) (graph[n].adj_list)

#define EndPoint(e) (e->endpoint)
#define ELabel(e)   (e->label)
#define ELabel2(e)  (e->label2)
#define Other(e)    (e->otheredge)
#define NextEdge(e) (e->nextedge)


extern Graph Prim();
extern int *EulerTraverse(),*Match(),*Weighted_Match(),*Dijkstra(),*Concomp();

/* Euclidean graph type */
typedef int (*EuclidGraph)[2];

extern Graph EuclidPrim();
extern EuclidGraph ReadEuclid(),NewEuclid();
extern int eucdist(),eucdistsq();

extern int *CvxHull();

/* Distance matrix graph type */
typedef int *MatrixGraph;

extern int *MatrixDijkstra();
extern Graph MatrixPrim();
extern Graph MatrixMaxFlow();
extern MatrixGraph ReadMatrix(), NewMatrix();

SHAR_EOF
fi
if test -f 'input.form'
then
	echo shar: "will not over-write existing file 'input.form'"
else
cat << \SHAR_EOF > 'input.form'
Disclaimer: the following description was obtained  by inspection of the
code and some simple tests.  It was not written by the implementor.  CCM

There will soon be available a program for translating from the DIMACS
standard format to this format.  Contributions are welcome. CCM

-------------------------------------------------------------------------
INPUT FORMAT FOR MATCH:
-------------------------------------------------------------------------
   Graph I/O is performed by a generic graph library package, 
   so some of the fields are ignored by the "match" code (but 
   you must include dummy fields in the input). 

   There are three types of lines: the first line, vertex lines, 
   and edge lines. The fields in each line type are as follows. 

   First line-> size edges U
      size: integer giving number of vertices
      edges: integer giving number of edges 
      U: character ``U'' or ``u'' specifying an undirected graph

   Vertex lines->  degree vlabel xcoord ycoord
      degree: edge degree of the vertex
      vlabel: vertex label (ignored--vertices are referred to by index)
      xcoord: integer x-coordinate location (ignored)
      ycoord: integer y-coordinate location (ignored) 

      *****Each vertex line is followed immediately by the lines 
      for all its adjacent edges (thus each edge appears twice, 
      once for each vertex).******

   Edge lines-> adjacent  label
      adjacent: index (not vlabel) of the adjacent vertex
      label: integer edge label (ignored)
     





SHAR_EOF
fi
if test -f 'main.c'
then
	echo shar: "will not over-write existing file 'main.c'"
else
cat << \SHAR_EOF > 'main.c'
#include "graphtypes.h"

main(argc,argv)
int argc;
char *argv[];

{	int *Mate;
	Graph graph;
	int i,size;

	graph = ReadGraph(&size,argv[1]);

	Mate = Match(graph);

	for (i=1; i<=size; i++)
		printf("%d %d\n",i,Mate[i]);
}

SHAR_EOF
fi
if test -f 'makefile'
then
	echo shar: "will not over-write existing file 'makefile'"
else
cat << \SHAR_EOF > 'makefile'
match: main.o match.o glib.o
	cc -o match main.o match.o glib.o -lm

SHAR_EOF
fi
if test -f 'match.c'
then
	echo shar: "will not over-write existing file 'match.c'"
else
cat << \SHAR_EOF > 'match.c'
/* N-cubed Non-weighted matching */
/* Implementation of H. Gabow's labelling scheme */
/* For an explanation of the algorithm see JACM 23, pp221-34 */
/* Written by Edward Rothberg 6/85 */



#include "graphtypes.h"

struct adj {
	int edge;
	struct adj *next;
	};

static struct adj **adj_list;
static struct adj *space;

static int U, V;   /* U = no. of nodes, V = no. of edges */
static int *MATE;  /* stores the mate of each vertex.  0 if vertex is exposed */
static int *FIRST; /* first non-outer vertex in the path back to the start of */
			/* the search */
static int *LABEL; /* multi-purpose label */
static int *OUTER; /* queue of outer vertices to be searched */

static int *END;   /* stores endpoints of edges */
static int qcount = 0;


int *Match (graph)
Graph graph;
{	int x,y,i,u,v,qptr=0;
	struct adj *p;

	U = Degree(graph,0);
	V = NumEdges(graph);

	/* set up matching data structure */
	Initialize (graph);

	/* start off with a greedy matching */
	Greedy();

	/* search for an augmenting path from each exposed node */
	for (u=1; u<=U; ++u) {
		if (MATE[u] != 0)
			continue;
		OUTER[++qcount] = u;
		LABEL[u] = 0;
		while (qcount != qptr) {  /* while queue is not empty */
			x = OUTER[++qptr];
			p = adj_list[x];
			while (p != NULL) {

				/* y is adjacent to an outer vertex */
				y = (END[p->edge]==x) ? END[p->edge-1] : END[p->edge];

				if (MATE[y] == 0 && y != u) {
					/* found an augmenting path */
					MATE[y] = x;
					REMATCH(x,y);
					qptr = qcount;
					break;
					}
				else if (LABEL[y] >= 0) {
					/* created a blossom */
					DOLABEL(x,y);
					}
				else {
					/* extended the search path */
					v = MATE[y];
					if (LABEL[v] < 0) {
						LABEL[v] = x;
						FIRST[v] = y;
						OUTER[++qcount] = v;
						}
					}
				p = p->next; 
			}
		}

		for (i=0; i<=U; ++i)
			LABEL[i] = -1;
		qcount = 0;
		qptr = 0;
		}
	FreeUp();
	return(MATE);
}


/* take input graph and set up matching data structure.  Matching uses a */
/* structure where each edge has a number, and the adjacency list entry  */
/* for an edge contains that number */

Initialize (graph)
Graph graph;

{	int i, j;
	int allocsize;
	int currentedge,adj_node;
	Edge edge;
	struct adj *p;

	currentedge = U+2;
	END = (int *) malloc((U+2*V+1)*(sizeof(int)));
	adj_list = (struct adj **) malloc((U+1)*(sizeof(struct adj *)));
	for (i=1; i<=U; i++)
		adj_list[i] = NULL;
	space = (struct adj *) malloc(2*V*sizeof(struct adj));
	p = space;
	for (i = 1; i <= U; ++i) {
		edge = FirstEdge(graph,i);
		for (j = 1; j <= Degree(graph,i); ++j) {
			adj_node = EndPoint(edge);
			if (i < adj_node) {
				END[currentedge-1] = i;
				END[currentedge] = adj_node;
				p->edge = currentedge;
				p->next = adj_list[i];
				adj_list[i]=p++;
				p->edge = currentedge;
				p->next = adj_list[adj_node];
				adj_list[adj_node] = p++;
				currentedge += 2;
				}
			edge = NextEdge(edge);
			}
		}

	allocsize = (U+1)*(sizeof(int));
	FIRST = (int *) malloc(allocsize);
	MATE  = (int *) malloc(allocsize);
	LABEL = (int *) malloc(allocsize);
	OUTER = (int *) malloc(allocsize);

	for (i = 0; i <= U; ++i) {
		LABEL[i] = -1;
		FIRST[i] = 0;
		MATE[i] = 0;
		}
}

FreeUp ()
{
	free(adj_list);
	free(space);
	free(END);
	free(FIRST);
	free(LABEL);
	free(OUTER);
}


/* greedy matching.  If a vertex is unmatched, check all adjacent vertices */
/* to see if any of them are also unmatched.  If so, match them. */

Greedy()
{	struct adj *p;
	int i,adj_node;

	for (i=1; i<=U; i++) {
		if (MATE[i]!=0)
			continue;
		p = adj_list[i];
		while (p!=NULL) {
			adj_node = (END[p->edge]!=i) ? 
					END[p->edge] : END[p->edge-1];
			if (MATE[adj_node]==0) {
				MATE[i] = adj_node;
				MATE[adj_node] = i;
				break;
				}
			p = p->next;
			}
		}
}


/* Augment the matching along the augmenting path defined by LABEL */

REMATCH(v,w)
int v,w;

{	int t,x,y;

	t = MATE[v];
	MATE[v] = w;
	if (MATE[t] != v)
		return;
	else if (LABEL[v] <= U) {
		MATE[t] = LABEL[v];
		REMATCH (LABEL[v], t);
		return;
		}
	else {
		x = END[LABEL[v]];
		y = END[LABEL[v]-1];
		REMATCH (x, y);
		REMATCH (y, x);
		return;
		}
}


/* Make all non-outer vertices in the blossom outer */
LabelSub (v,edge,join)
int v,edge,join;

{
	while (v != join) {
		LABEL[v] = edge;
		FIRST[v] = join;
		OUTER[++qcount] = v;
		v = FIRST[LABEL[MATE[v]]];
		}
}


/* return the number of the edge between x and y */
Findedge (x,y)
int x,y;

{	int edge;
	struct adj *p;

	p = adj_list[x];
	while (p != NULL) {
		edge = p->edge;
		if (END[edge] == y || END[edge-1] == y)
			return(edge);
		p = p->next;
		}
	return(0);
}


/* x and y are adjacent and both are outer.  Create a blossom. */

DOLABEL (x,y)
int x,y;

{	int r,s;
	int edge, flag, join;
	register temp;
    
	edge = Findedge (x,y);
	flag = -edge;
	r = FIRST[x];
	s = FIRST[y];
	if (r == s)
		return;
	LABEL[r] = flag;
	LABEL[s] = flag;

	if (s != 0) {
		temp = r;
		r = s;
		s = temp;
		}
    
	r = FIRST[LABEL[MATE[r]]];

	while (LABEL[r] != flag) {
		LABEL[r] = flag;
		if (s != 0) {
			temp = r;
			r = s;
			s = temp;
			}
		r = FIRST[LABEL[MATE[r]]];
		}

	join = r;

	LabelSub(FIRST[x], edge, join);
	LabelSub(FIRST[y], edge, join);

	for (s = 1; s <= qcount; s++)
		if (LABEL[FIRST[OUTER[s]]] > 0)
			FIRST[OUTER[s]] = join;

}

SHAR_EOF
fi
if test -f 'output.form'
then
	echo shar: "will not over-write existing file 'output.form'"
else
cat << \SHAR_EOF > 'output.form'
Disclaimer: the following description was obtained by inspection of the
code and some simple tests.  It was not written by the implementor.  CCM

There will soon be available a program for translating from this output
format to the DIMACS standard format.  Contributions are welcome.  CCM
----------------------------------------------------------------------
OUTPUT FORMAT FOR WMATCH
----------------------------------------------------------------------

The i-th line:  Contains the i-th vertex and its mate.
				If the first entry is 0, the i-th vertex is unmatched.
 
  For example:
            1 3
            2 4 
            3 1
            4 2
            5 6
            6 5



SHAR_EOF
fi
if test -f 'test.in'
then
	echo shar: "will not over-write existing file 'test.in'"
else
cat << \SHAR_EOF > 'test.in'
6 8 U
2 3 0 0 
2 6
3 8
3 3 0 0 
1 6 
5 3
4 6
3 3 0 0 
1 8
4 3
5 3
3 3 0 0 
2 6
3 3
6 8
3 3 0 0 
3 3
2 3
6 6
2 3 0 0 
4 8
5 6

SHAR_EOF
fi
exit 0
#   End of shell archive
